大家好!
今天给大家带来的是第74题搜索二维矩阵
![第74题图](https://img-blog.csdnimg.cn/20210330175336306.png?x-oss-process=i
mage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG
4ubmV0L1NHQ1RTR0NU,size_16,color_FFFFFF,t_70)
 传送门: [https://leetcode-cn.com/problems/search-a-2d-matrix/](https://leetc
ode-cn.com/problems/search-a-2d-matrix/)
这个题其实一看就知道是二分,因为他都把升序写到脸上了,关键是二分的方法.
有两种方法来进行二分查找:
- 先对行进行查找,定位到行,再在行内进行查找,两次二分
- 直接将所有的数据看成一个整体(即假想将所有数据拉平),一次二分
这两种方法其实没有什么本质复杂度的区别,都是O(lg(m*n)),而第一种方法看起来就复
杂很多,因为还要判断存不存在这种问题,还得处理两遍二分,就比较复杂,所以我们着重
使用第二种方法.  
这是一个m*n的数组,我们假设将其按照顺序展平,成为一个一维数组,(将第二行接在第一
行的最后).按照题目的描述,这样展开之后的元素还是有序的,既然是有序的,太方便了,
直接二分就出答案了.给大家上个代码品品
```cpp
class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size(), left = 0, right = m * n 
        - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[mid / n][mid % n] == target) return true;
            else if (matrix[mid / n][mid % n] > target) right = mid - 1;
            else left = mid + 1;
        }
        return false;
    }
};
```
这个二分查找非常的简单,关键就是把数组摊平的想法.假想中的数组长度是`m*n`,`left
`是`0`,`right`是`m*n-1`,这个都好理解,我们在获得了平面数组的位置`mid`之后还得
在原来的矩阵中找到对应的值,一行有`n`个元素,`mid/n`就是该元素所在的行数,mid%n
就是该元素在行中的位置(即为列数),这个二分还是一个查找定值的二分,找到了直接退
出循环,找不到的话就可以跳过`mid`,因为`mid`永远不是`target`.
有一点非常生气,B站的编辑器竟然不支持rust,只能随意选了个js发了
```rust
impl Solution {
    pub fn search_matrix(matrix: Vec>, target: i32) -> bool {
        let (m, n) = (matrix.len(), matrix[0].len());
        let (mut left, mut right) = (0, (m * n - 1) as i32);
        while (left <= right) {
            let mid = (left + right) / 2;
            if matrix[mid as usize / n][mid as usize % n] == target {